import java.util.Stack;

public class Solution {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    // 二叉树的最近公公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(p==root || q==root){
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if(leftRet!=null && rightRet!=null){
            return root;
        }else if(leftRet != null){
            return leftRet;
        }else{
            return rightRet;
        }

    }
    // 二叉树的最近公公共祖先,法二
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        getPath(root,p,s1);
        getPath(root,q,s2);
        int size1 = s1.size();
        int size2 = s2.size();
        if(size1 > size2){
            int size = size1-size2;
            while (size!=0){
                s1.pop();
                size--;
            }
        }else {
            int size = size2-size1;
            while (size!=0){
                s2.pop();
                size--;
            }
        }
        if(!s1.empty()&&!s2.empty()){
            TreeNode tmp1 = s1.pop();
            TreeNode tmp2 = s2.pop();
            if(tmp1==tmp2){
                return tmp1;
            }
        }
        return null;

    }
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean ret = getPath(root.left,node,stack);
        if(ret == true){
            return true;
        }
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2 == true){
            return  true;
        }
        stack.pop();
        return false;
    }
    // 二叉树的前序遍历----> 非递归
    public void preorderTraversal(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null||!stack.empty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    //二叉树的中序遍历----> 非递归
    public void inOrder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null||!stack.empty()){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(cur.val+" ");
            cur = top.right;
        }
    }
    //二叉树的后序遍历----> 非递归
    public void postOrder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null||!stack.empty()){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            TreeNode pre = null;
            if(top.right!=null || top.right == pre){
                System.out.print(top.val+" ");
                pre = top;
                stack.pop();
            }else{
                cur = top.right;
            }

        }
    }
    // 根据二叉树创建字符串
    public String tree2str(TreeNode root){
        if(root == null) return null;
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if(root == null) return;
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if(root.right==null){
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        if(root.right!=null){
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }

}
